6、七段码
题目 七段码
思路分析
二极管 不外乎就是亮与不亮 可以联想到用二进制来表示
每个二进制位来表示一段二极管
a b c d e f g
1 2 3 4 5 6 7
1 1 1 1 1 1 1
要连续的发光才合法
所以问题应该就是转变成了 0000000~1111111中有多少个
满足
亮一个 1 2 3 4 5 6 7 上为1
亮两个 1,2 1,6 2,3 2,7 3,4 3,7 4,5 5,6 5,7 6,7 位上同时为1
……
#include<bits/stdc++.h>
using namespace std;
bool check(int x){
bitset<8> temp(x);
string s=temp.to_string();
if((s[0]==s[1] && s[0]=='1')
||
(s[0]==s[5] && s[0]=='1')
||
(s[1]==s[2] && s[1]=='1')
||
(s[1]==s[6] && s[1]=='1')
||
(s[2]==s[3] && s[2]=='1')
||
(s[2]==s[6] && s[2]=='1')
||
(s[3]==s[4] && s[3]=='1')
||
(s[4]==s[5] && s[4]=='1')
||
(s[4]==s[6] && s[4]=='1')
||
(s[5]==s[6] && s[5]=='1')
//…………一个的情况 两个的情况 三个的情况
)
return true;
return false;
}
int main()
{
long long cnt=0;
for(int i=0;i<(1<<7);i++)
if(check(i))
cnt++;
cout<<cnt;
return 0;
}
这还写什么代码 还不如手算出来了
这里代码可以借鉴的东西就是 可以把一个十进制数用bitset转变成二进制数
再把二进制数 用.to_string()方法转变成字符串处理
直接可以手写了 方案数不多
亮一个灯:1、2、3、4、5、6、7，共7种 亮两个灯:12、13、24、25、34、36、45、46、57、67，共10种 亮三个灯:123、124、125、134、136、234、245、246、257、345、346、367、456、457、467、567，共16种 亮四个灯，这时不要直接数四个灯，情况与灭三个灯是等价的，数三个灯比数四个灯简单。注意灭三个灯后其他的四个亮灯是连续的:灭123、124、125、126、127、134、135、136、137、157、167、245、257、267、346、357、367、457、467、567，共20种 亮五个灯:数灭两个灯的情况:灭12、灭13、灭14、…等，共19种 亮六个灯:数灭一个灯的情况，有7种 亮七个灯:有1种 共80种
正解应该是dfs
又是想到二进制枚举结果给我dfs 啧
将7段码数码管的每个段视为图的一个节点，节点之间的连通关系表示为图的边
问题转化为了在一个由7个节点构成的图中，找出所有点亮的节点形成单个连通分量的组合
每个段都有点亮和不点亮两种状态，指数型枚举
在每个DFS的递归调用中，利用并查集来检查当前点亮的段是否都在同一个连通分量中，路径压缩，快速判断当前点亮的所有段是否能够通过已有的边相连，形成一个连通分量
这题dfs比较容易想 主要是并查集有点生疏
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 10;
int g[N][N]; // 邻接矩阵，表示数码管各段之间的连通关系
int p[N]; // 并查集的父节点数组
bool st[N];
int res;
// 添加边，即设置数码管的两个段是相连的
void add(int a, int b) {
g[a][b] = g[b][a] = 1;
}
// 并查集查找函数,路径压缩
int find(int x) {
if(p[x] != x)
return p[x] = find(p[x]);
return p[x];
}
// 检查当前点亮的数码管段是否形成单个连通分量
bool check() {
for(int i = 1; i <= 7; i++)
p[i] = i; // 初始化并查集
for(int i = 1; i <= 7; i++) {
for(int j = 1; j <= 7; j++) {
if(st[i] && st[j] && g[i][j])
p[find(j)] = find(i); // 合并连通的段
}
}
int cnt = 0;
for(int i = 1; i <= 7; i++)
if(st[i] && p[i] == i)
cnt++; // 计算连通分量数量
return cnt == 1; // 只有当存在一个连通分量时，返回true
}
void dfs(int u) {
if(u > 7) {
if(check())
res++;
return;
}
st[u] = true;
dfs(u + 1);
st[u] = false;
dfs(u + 1);
}
int main() {
// 设置数码管段之间的连通关系
add(1,2); add(1,6);
add(2,3); add(2,7);
add(3,4); add(3,7);
add(4,5); add(5,6); add(5,7);
add(6,7); add(6,1);
dfs(1);
cout<<res<<endl;
return 0;
}
💬 评论